package com.yitiao.data_algorithms.leetcode.editor.cn;

class ErChaSouSuoShuDeHouXuBianLiXuLieLcof {
    // 2023-02-08 17:52:54
    public static void main(String[] args) {
        Solution solution = new ErChaSouSuoShuDeHouXuBianLiXuLieLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 数组的最后一个元素一定是根节点。
        // 然后找到第一个大于根节点的元素，就找到了右子树的第一个节点，
        public boolean verifyPostorder(int[] postorder) {

            return dfs(postorder, 0, postorder.length - 1);
        }

        private boolean dfs(int[] postorder, int l, int r) {
            if (l >= r) return true;

            int root = postorder[r];
            int t = l;  // 指针
            while (postorder[t] < root) {
                t++;
            }
            // 记录第一个比root大的位置，即右子树开始的位置
            int p = t;
            while (t < r) {
                t++;
                if (postorder[t] < root) {
                    return false;
                }
            }
            return dfs(postorder, l, p - 1) && dfs(postorder, p, r - 1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}